package search;

import java.util.LinkedList;

public class BFS {

    /**
     * 1091. 二进制矩阵中的最短路径
     * 给你一个 n x n 的二进制矩阵 grid 中，返回矩阵中最短 畅通路径 的长度。如果不存在这样的路径，返回 -1 。
     * <p>
     * 二进制矩阵中的 畅通路径 是一条从 左上角 单元格（即，(0, 0)）到 右下角 单元格（即，(n - 1, n - 1)）的路径，该路径同时满足下述要求：
     * <p>
     * 路径途经的所有单元格都的值都是 0 。
     * 路径中所有相邻的单元格应当在 8 个方向之一 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。
     * 畅通路径的长度 是该路径途经的单元格总数。
     *
     * @param grid
     * @return
     */
    public int shortestPathBinaryMatrix(int[][] grid) {
        LinkedList<PathNode> queue = new LinkedList<>();
        if (grid.length == 0 || grid[0].length == 0 || grid[0][0] == 1 || grid[grid.length - 1][grid[0].length - 1] == 1) {
            return -1;
        }
        queue.addLast(new PathNode(0, 0, 1));
        grid[0][0] = 1;
        // 可行的八个位置
        int[][] positions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}, {-1, -1}, {0, 1}, {1, 1}, {1, -1}};
        while (!queue.isEmpty()) {
            // 当前节点
            PathNode node = queue.removeFirst();
            for (int i = 0; i < positions.length; i++) {
                int x = node.x + positions[i][0];
                int y = node.y + positions[i][1];
                if (isValiable(x, y, grid) && grid[x][y] == 0) {
                    queue.addLast(new PathNode(x, y, node.total + 1));
                    grid[x][y] = node.total + 1;
                }
                if (x == grid.length-1 && y == grid[0].length-1) {
                    return grid[x][y];
                }
            }
        }
        return -1;
    }

    private boolean isValiable(int x, int y, int[][] grid) {
        if (0 <= x && x < grid.length && 0 <= y && y < grid[0].length)
            return true;
        return false;
    }

    class PathNode {
        int x, y, total;

        PathNode(int x, int y, int total) {
            this.x = x;
            this.y = y;
            this.total = total;
        }
    }

    public static void main(String[] args) {
        int[][] grid = new int[][]{{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
        int total = new BFS().shortestPathBinaryMatrix(grid);
        System.out.println(total);
    }
}
